import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

class InternalNode extends Node {
    List<Integer> key;
    List<Node> son;
    int sonNum;

    InternalNode(int n, InternalNode father) {
        key = new LinkedList<>();
        son = new LinkedList<>();
        this.father = father;
        sonNum = n;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("内节点").append(count).append(" ");
        builder.append("   键值[");
        for (int k : key) {
            builder.append(k).append(" ");
        }
        builder.append("]  儿子[");
        for (Node n : son) {
            builder.append(n.count).append(" ");
        }
        if (father != null)
            builder.append("]  父节点").append(father.count).append("\n");
        else
            builder.append("]\n");
        return builder.toString();
    }

    public NodeKey insert(int key, Node newSon) {
        if (this.isFull()) {
            int loc = this.key.size();
            for (int i = 0; i < this.key.size(); i++)
                if (key < this.key.get(i)) {
                    loc = i;
                    break;
                }
            this.key.add(loc, key);
            this.son.add(loc + 1, newSon);
            newSon.father = this;

            int median = this.sonNum / 2;
            InternalNode newNode = new InternalNode(this.sonNum, this.father);
            int full_size = this.key.size();
            int medianKey = this.key.remove(median);
            Node temp = this.son.remove(median + 1);
            newNode.son.add(temp);
            temp.father = newNode;
            for (int i = median + 1; i < full_size; i++) {
                newNode.key.add(this.key.remove(median));
                temp = this.son.remove(median + 1);
                newNode.son.add(temp);
                temp.father = newNode;

            }
            return new NodeKey(newNode, medianKey);
        } else {
            int loc = this.key.size();
            for (int i = 0; i < this.key.size(); i++)
                if (key < this.key.get(i)) {
                    loc = i;
                    break;
                }
            this.key.add(loc, key);
            this.son.add(loc + 1, newSon);
            newSon.father = this;
            return null;
        }
    }

    /**
     * 删除指定位置的索引
     *
     * @param newIndex 要删除的索引的位置，一并删除相同位置的指针
     */
    public Node delete(int newIndex) {
        boolean loop = this.isNearUnder();
        Node result = null;
        this.key.remove(newIndex);
        this.son.remove(newIndex + 1);
        if (father != null && loop) {
            int index = this.getIndex();
            if (index > 0 && !father.son.get(index - 1).isNearUnder()) {
                InternalNode leftsib = (InternalNode) father.son.get(index - 1);
                int modifiedKey = leftsib.key.remove(leftsib.key.size() - 1);
                Node modifiedNode = leftsib.son.remove(leftsib.son.size() - 1);
                this.key.add(0, father.key.get(index - 1));
                this.son.add(0, modifiedNode);
                modifiedNode.father = this;
                father.modifyIndex(modifiedKey, index - 1);
            } else if (index < father.son.size() - 1 && !father.son.get(index + 1).isNearUnder()) {
                InternalNode rightsib = (InternalNode) father.son.get(index + 1);
                int modifiedKey = rightsib.key.remove(0);
                Node modifiedNode = rightsib.son.remove(0);
                this.key.add(father.key.get(index));
                this.son.add(modifiedNode);
                modifiedNode.father = this;
                father.modifyIndex(modifiedKey, index);
            } else if (index > 0) {
                InternalNode leftsib = (InternalNode) father.son.get(index - 1);
                leftsib.merge(this);
                result = father.delete(index - 1);
            } else if (index < father.son.size() - 1) {
                this.merge(father.son.get(index + 1));
                result = father.delete(index);
            }
        }
        if (father == null && key.size() == 0) {
            result = son.get(0);
        }
        return result;
    }

    /**
     * 修改节点的索引
     *
     * @param key   新的索引值
     * @param index 修改的位置
     */
    void modifyIndex(int key, int index) {
        this.key.set(index, key);
    }

    public boolean isFull() {
        return this.son.size() == this.sonNum;
    }

    @Override
    public boolean isNearUnder() {
        return (this.son.size() - 1) < this.sonNum * 0.5;
    }

    public Node getSon(int i) {
        return this.son.get(i);
    }

    public InternalNode getFather() {
        return father;
    }

    public int getKey(int i) {
        return this.key.get(i);
    }

    @Override
    void merge(Node n) {
        assert n instanceof InternalNode;
        InternalNode i = (InternalNode) n;
        int index = i.getIndex();
        int newKey = i.father.key.get(index - 1);
        this.key.add(newKey);
        Iterator<Integer> keyIt = i.key.iterator();
        Iterator<Node> nodeIt = i.son.iterator();
        Node newSon = nodeIt.next();
        this.son.add(newSon);
        newSon.father = this;//node比索引多一个
        while (keyIt.hasNext()) {
            this.key.add(keyIt.next());
            newSon = nodeIt.next();
            this.son.add(newSon);
            newSon.father = this;
        }
    }
}
